﻿#include"mazestack.h"



//初始化一个栈区
PtrMazeStackHead InitMazeStackHead()
{
	PtrMazeStackHead ptr = (PtrMazeStackHead)malloc(sizeof(MazeStackHead));
	ptr->fistelem = NULL;
	ptr->size = 0;
	return ptr;
}

//初始化一个栈区元素
PtrMazeStackelem InitMazeStackElem(int row, int col)
{
	PtrMazeStackelem ptr = (PtrMazeStackelem)malloc(sizeof(MazeStackelem));
	ptr->row = row;
	ptr->col = col;
	ptr->next = NULL;
	return ptr;
}


//放入一个迷宫地址元素
void push_Mazeelem(PtrMazeStackHead Head1, int row, int col)
{
	assert(Head1);
	if (row < 0 || col < 0)return;
	Head1->size++;
	if (!Head1->fistelem)
	{
		Head1->fistelem = InitMazeStackElem(row, col);
	}
	else
	{
		PtrMazeStackelem next = Head1->fistelem;
		Head1->fistelem = InitMazeStackElem(row, col);
		Head1->fistelem->next = next;	
	}
	return;
}

//出栈一个迷宫地址元素 通过row col接收（head至少有一个元素）
void pop_Mazeelem(PtrMazeStackHead Head1, int* row, int* col)
{
	assert(Head1);
	assert(Head1->fistelem);
	Head1->size--;
	PtrMazeStackelem firstelem = Head1->fistelem;
	*row = firstelem->row;
	*col = firstelem->col;
	Head1->fistelem = firstelem->next;
	free(firstelem);
	firstelem = NULL;
}

//获取一个迷宫地址元素 返回元素地址
 const PtrMazeStackelem Get_FirstMazeelem(const PtrMazeStackHead Head1)
{
	assert(Head1);
	return  Head1->fistelem;
}


 //判断栈区是否为空 return 1为空 0为不空
 U8 IsStackEmpty(const PtrMazeStackHead Head1)
 {
	 assert(Head1);
	 return (Head1->size > 0) ? 0 : 1;
 }



 //清空栈区
 void ClearMazeStack(PtrMazeStackHead Head1)
 {
	 assert(Head1);
	 Head1->size = 0;
	 PtrMazeStackelem firstelem = Head1->fistelem;
	 PtrMazeStackelem Nextelem = NULL;
	 while (firstelem)
	 {
		 Nextelem = firstelem->next;
		 free(firstelem);
		 firstelem = Nextelem;
	 }
	 Head1->fistelem = NULL;
 }

 //摧毁栈区
 void DestoryMazeStack(PtrMazeStackHead *Head1)
 {
	 assert(*Head1);
	 ClearMazeStack(*Head1);
	 free(*Head1);
	 *Head1 = NULL;
 }

 //获得栈区大小
 U8 GetStackSize(const PtrMazeStackHead Head1)
 {
	 assert(Head1);
	 return Head1->size;
 }

 //******************************************随机迷宫版本************************************//

 //初始化一个迷宫
 void InitMaze(char(*MazeMap1)[RANDMAZEMAXCOL])
 {
	 assert(MazeMap1);
	 //将所有空间初始化为墙
	 for (int i = 0; i < RANDMAZEMAXROW ; i += 1)
	 {
		 for (int j = 0; j < RANDMAZEMAXCOL ; j += 1)
		 {
			 MazeMap1[i][j] = WALL;
		 }
	 }
	//初始化未探索空间
	 for (int i = 2; i < RANDMAZEMAXROW - 2; i += 2)
	 {
		 for (int j = 2; j < RANDMAZEMAXCOL - 2; j += 2)
		 {
			 MazeMap1[i][j] = UN_SEACH;
		 }
	 }
  }


 //打印随机生成的地图
 void ShowRandMaze(const char(*MazeMap1)[RANDMAZEMAXCOL])
 {
	 for (int row = 0; row < RANDMAZEMAXROW; row++)
	 {
		 for (int col = 0; col < RANDMAZEMAXCOL; col++)
		 {
			 switch (MazeMap1[row][col])
			 {
			 case WALL:
				 //白色
				 printf("\033[0;37;47mOO\033[m");
				 break;
			 case ROAD:
				 //黑色
				 printf("\033[0;30;40mOO\033[m");
				 break;
			 case EXIT:
				 //黄色
				 printf("\033[0;33;43mOO\033[m");
				 break;
			 case HAS_PASSED:
				 //蓝色
				 printf("\033[0;34;44mOO\033[m");
				 break;
			 case REAL_WAY:
				 //红色
				 printf("\033[0;31;41mOO\033[m");
				 break;
			 case UN_SEACH:
				 //空格
				 printf("  ");
				 break;
			 default:
				 break;
			 }
		 }
		 printf("\n");
	 }
 }


 //判断是否还有没有寻找过得路径
 int IsHaveUnsearch(const char(*MazeMap1)[RANDMAZEMAXCOL])
 {
	 assert(MazeMap1);
	 for (int i = 2; i < RANDMAZEMAXROW-2; i+=2)
	 {
		 for (int j = 2; j < RANDMAZEMAXCOL-2; j+=2)
		 {
			 if (MazeMap1[i][j] == UN_SEACH)return 1;
		 }
	 }
	 return 0;
 }


 //判断坐标周围是否还有没有寻找过得路径
 int IsNearHaveUnsearch(const char(*MazeMap1)[RANDMAZEMAXCOL], const int row, const int col)
 {
 
	 if (MazeMap1[row][col+2] == UN_SEACH|| 
		 MazeMap1[row + 2][col] == UN_SEACH|| 
		 MazeMap1[row][col - 2] == UN_SEACH|| 
		 MazeMap1[row - 2][col] == UN_SEACH)return 1;//右，下，左，上
	 else return 0;
  }


 //随机选择一个方向
 enum dir randmovedir(const char(*MazeMap1)[RANDMAZEMAXCOL], const int row, const int col)
 {
	 enum dir dir1 = rand()%4+1;
	 int i = 1;
	 while (i)
	 {
		 switch (dir1)
		 {
		 case UP:
			 if (MazeMap1[row - 2][col] == UN_SEACH)i = 0;
			 break;
		 case DOWN:
			 if(MazeMap1[row + 2][col] == UN_SEACH)i = 0; 
			 break;
		 case LEFT:
	         if (MazeMap1[row][col - 2] == UN_SEACH)i = 0;
			 break;
		 case RIGHT:
			 if (MazeMap1[row][col + 2] == UN_SEACH)i = 0;
			 break;
		 default:
			 break;
		 }

		 if(i) dir1 = rand() % 4 + 1;
	 }
	 return dir1;
 }





 //创造一个随机地图（深度优先）
 void CreateMaze(char(*MazeMap1)[RANDMAZEMAXCOL], PtrMazeStackHead Head1,int speed)
 {
	 //判断输入合法
	 assert(MazeMap1);
	 assert(Head1);
	 assert(!Head1->size);
	 //最小行列
	 assert(RANDMAZEMAXROW > 10 || RANDMAZEMAXCOL > 10);
	 //行列必须为奇数
	 assert(RANDMAZEMAXROW % 2 && RANDMAZEMAXCOL && 2);
	 //设置起点
	 int nowrow = 2;
	 int nowcol = 2;
	 //记录方向
	 enum dir dir1;
	 //是否有，没有搜索过得位置
	 while (IsHaveUnsearch(MazeMap1))
	 {
		 //判断当前位置附近是否有没探索过得区域
		 if (IsNearHaveUnsearch(MazeMap1, nowrow, nowcol))
		 {
			 //随机个方向
			 dir1 = randmovedir(MazeMap1, nowrow, nowcol);
			 //当前地址压栈
			 push_Mazeelem(Head1, nowrow, nowcol);
		     //更具方向打开两个地点隔离的墙
			 switch (dir1)
			 {
			 case UP:
				 MazeMap1[nowrow-1][nowcol] = ROAD;
				 break;
			 case DOWN:
				 MazeMap1[nowrow+1][nowcol] = ROAD;
				 break;
			 case LEFT:
				 MazeMap1[nowrow][nowcol-1] = ROAD;
				 break;
			 case RIGHT:
				 MazeMap1[nowrow][nowcol+1] = ROAD;
				 break;
			 }
			 //将探索过得标记成路
			 MazeMap1[nowrow][nowcol] = ROAD;
			
#ifdef showCreat
			 ShowRandMaze(MazeMap1);
			 Sleep(speed);
			 system("cls");
#endif // showCreat

			 //更具方向移动
			 switch (dir1)
			 {
			 case UP:
				 nowrow-=2;
				 break;
			 case DOWN:
				 nowrow+=2;
				 break;
			 case LEFT:
				 nowcol-=2;
				 break;
			 case RIGHT:
				 nowcol+=2;
				 break;
			 }
		 
		 }
		 else//判断当前位置附近没有可探索区域
		 {
			 //栈不为空
			 if (!IsStackEmpty(Head1))
			 {
				 //记录栈顶地址并且出栈
				 int tmp1 = -1;
				 int tmp2 = -1;
				 pop_Mazeelem(Head1, &tmp1, &tmp2);
				 //将当前位置更新为路
				 MazeMap1[nowrow][nowcol] = ROAD;
				 //将当前位置更新为栈顶元素
				 nowrow = tmp1;
				 nowcol = tmp2;
			 }
		 }
		 //栈为空时所有探索过了
		 if (IsStackEmpty(Head1))break;
	 }
	 //放入出口
	 MazeMap1[RANDMAZEMAXROW - 3][RANDMAZEMAXCOL - 3] = EXIT;
 }









 //寻找出口路径并显示寻找过程
 void SerchMazeWay(char MazeMap1[RANDMAZEMAXROW][RANDMAZEMAXCOL], PtrMazeStackHead Head1, int speed)
 {
	
	 //判断栈区是否存在且为空
	 assert(Head1);
	 assert(!(Head1->size));
	 //设置起始坐标
	 int nowrow = 2;
	 int nowcol = 2;
	 //第一个标量储存方位
	 enum dir dir1 = NO;
	 do
	 {
		 //获取当前坐标的情况
		 char brock = MazeMap1[nowrow][nowcol];
		 //如果是可以走的
		 if (brock == ROAD || brock == EXIT)
		 {
			 //如果是路
			 if (brock == ROAD)
			 {
				 //将这个路的坐标压栈
				 push_Mazeelem(Head1, nowrow, nowcol);
				 //将这个路的坐标给改为确定路线
				 MazeMap1[nowrow][nowcol] = REAL_WAY;
				 //展示当前行进位置
#ifdef showsearch
				 ShowRandMaze(MazeMap1);
				 Sleep(speed);
				 system("cls");
#endif // showsearch

				 
			 }
			 if (brock == EXIT) //如果是出口就退出 栈区中存储确定的路线
			 {
				 ShowRandMaze(MazeMap1);
				 printf("找到了");
				 return;
			 }
			 else//如果不是出口
			 {
				 //默认向右走寻路
				 nowcol++;
			 }
		 }
		 else//如果是不能走的
		 {
			 //记录栈区顶部的第一个坐标
			 PtrMazeStackelem firstelem = Get_FirstMazeelem(Head1);
			 int firstrow = firstelem->row;
			 int firstcol = firstelem->col;
			 //当栈区不为空（为空时就没有出口）并且顶部的第一个坐标周边方向可以走
			 if (!IsStackEmpty(Head1) && (dir1 = Is_Randcanmove(MazeMap1, firstelem)) != NO)
			 {
				 //将坐标更新为栈顶坐标
				 nowrow = firstrow;
				 nowcol = firstcol;
				 switch (dir1)
				 {
				 case UP:
					 nowrow--;
					 break;
				 case DOWN:
					 nowrow++;
					 break;
				 case LEFT:
					 nowcol--;
					 break;
				 case RIGHT:
					 nowcol++;
					 break;
				 default:
					 break;
				 }
			 }
			 //当栈区不为空（为空时就没有出口）并且顶部的第一个坐标周边无方向可以走
			 if (!IsStackEmpty(Head1) && dir1 == NO)
			 {
				 while (!IsStackEmpty(Head1))
				 {
					 //记录栈区顶部的第一个坐标
					 firstelem = Get_FirstMazeelem(Head1);
					 //判断顶部的第一个坐标周边方向是否可以走
					 dir1 = Is_Randcanmove(MazeMap1, firstelem);
					 if (dir1 == NO)
					 {
						 //扔出栈顶坐标 
						 pop_Mazeelem(Head1, &firstrow, &firstcol);
						 //将栈顶坐标标记为已经找过，并且一步
						 nowrow = firstrow;
						 nowcol = firstcol;
						 MazeMap1[nowrow][nowcol] = HAS_PASSED;
#ifdef showsearch
						 ShowRandMaze(MazeMap1);
						 Sleep(speed);
						 system("cls");
#endif // showsearch
					 }
					 else break;//可以走就退出
				 }
			 }
		 }
	 } while (!IsStackEmpty(Head1));
	 //此时栈区为空
	 ShowRandMaze(MazeMap1);
	 printf("无出口！");
	 
	 return;
 }





 //判断当前位置是否周边是否还能走并返回可以走的方向 
 enum dir Is_Randcanmove(const char(*MazeMap1)[RANDMAZEMAXCOL], const PtrMazeStackelem Elem)
 {
	 assert(Elem);
	 const int nowrow = Elem->row;
	 const int nowcol = Elem->col;
	 if (MazeMap1[nowrow][nowcol + 1] == ROAD || MazeMap1[nowrow][nowcol + 1] == EXIT)return RIGHT;
	 else if (MazeMap1[nowrow + 1][nowcol] == ROAD || MazeMap1[nowrow + 1][nowcol] == EXIT)return DOWN;
	 else if (MazeMap1[nowrow][nowcol - 1] == ROAD || MazeMap1[nowrow][nowcol - 1] == EXIT)return LEFT;
	 else if (MazeMap1[nowrow - 1][nowcol] == ROAD || MazeMap1[nowrow - 1][nowcol] == EXIT)return UP;
	 else
	 {
		 return NO;
	 }
 }
